package preSum

import (
	. "GoLeetcode/common"
)

/*
时间复杂度：O(N)
空间复杂度：O(N)

前缀和+hash

*/

func findMaxLength(nums []int) int {
	sum := 0
	ans := 0
	hash := make(map[int]int)
	// 因为如果nums[0，1]满足条件，此时索引为1，但长度为2，所以需要初始化hash[0]=-1
	hash[0] = -1
	for i, v := range nums {
		if v == 0 {
			sum += -1
		} else {
			sum += 1
		}
		if preIndex, ok := hash[sum]; ok {
			ans = Max(ans, i-preIndex)
		} else {
			hash[sum] = i
		}
	}
	return ans
}
